package ljl.alg.jianzhioffer.round2;

public class _19_pattern_match {
    
    /**
     * 用递归实现一把吧，然后白天就到这了
     * 晚上再看动态规划的内容
     *
     * 我的妈呀
     * 改了好几个小时，最终通过了所有测试用例，真是不容易
     *
     * 根据北邮那小子的方法改了一版，从 1440ms -> 24ms
     * 挺好
     * 多学！
     * */
    public boolean isMatch2(String s, String p) {
        return match(s, 0, p, 0);
    }
    boolean match(String s, int i, String p, int j) {
        if (j == p.length())
            return i == s.length();
        
        boolean firstMatch = i < s.length() && (p.charAt(j) == '.' || s.charAt(i) == p.charAt(j));
        if (j < p.length() - 1 && p.charAt(j + 1) == '*') {
            return firstMatch && match(s, i + 1, p, j) || match(s, i, p, j + 2);
        } else
            return firstMatch && match(s, i + 1, p, j + 1);
    }
    
    /**
     * 一个北邮的、在腾讯工作的提供的题解。
     *
     * 人家都财富自由了
     * 而我，还他妈的，在想玩啥游戏！
     * 傻屄！
     * 去你妈的！
     * */
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) return s.isEmpty();
        boolean firstMatch = s.length() > 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0));
        if (p.length() > 1 && p.charAt(1) == '*') {
            /*
            * 我忽然发现，这两种情况可以覆盖掉 isMatch(s.substring(1), p) || isMatch(s.substring(1), p.substring(2))
            * */
            return firstMatch && isMatch(s.substring(1), p)
                || isMatch(s, p.substring(2));
        } else
            return firstMatch && isMatch(s.substring(1), p.substring(1));
    }
    
    /**
     * 这个是使用动态规划
     * 思路和递归是非常类似的
     * 但是不是那么好想，需要很高的技巧
     *
     * 希望你早日掌握这个技巧！致未来的自己。
     * */
    public boolean isMatch_final(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 2; i <= n; i+= 2) {
            dp[0][i] = dp[0][i - 2] && p.charAt(i - 1) == '*';
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = p.charAt(j - 1) == '*' ?
                    dp[i][j-2] || dp[i - 1][j] && (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) :
                    dp[i - 1][j - 1] && (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1));
            }
        }
        return dp[m][n];
    }
}
